1. Field of the Invention
The present invention relates to computer systems and especially to computer systems with virtual addressing.
2. Description of the Related Art
Virtual addressing has been known for a while from the field of workstations. By using a certain mapping regulation virtual addresses are mapped to physical addresses. The physical addresses address memory cells of a physical memory, such as the working memory, a hard drive, a tape memory, etc. Virtual addresses however, do not reference directly to physical memory cells but merely indirectly via the mapping regulation. It is the advantage of this type of addressing that the programmer of an application does not have to take care of the different physical memories present in a computer system. The programmer has a virtual address space at his hands that he can use for his program as required. The mapping to the physical address space that a special computer system makes available is generated separately from the program code so that by making available different mapping regulations a program programmed with virtual addresses can run on different computer systems.
In a processor with a virtual memory system an application runs in a so-called virtual address space. Each address of the virtual memory where data read/writable by the application or executable code exist is mapped to an address on the physical memory where those data or this code is actually stored. The virtual address (VA) and the physical address (PA) associated via the mapping regulation do not need to have any relation at all. Further, the virtual address space can be significantly larger than the physical address space.
Virtual addresses without read/writable data or executable code are normally not mapped to a physical memory. This mapping is totally transparent for the processed application.
When organizing the memory in pages, the virtual address space is divided into equal overlapping-free memory areas. One page in the physical address space is associated to a page in the virtual address space via the mapping regulation; the page in the physical address space is also referred to as page frame.
The payload data memory of a page frame of the physical address space has the same size as a page of the virtual address space.
The allocation of a virtual page to a physical page is usually achieved by the so-called page table, comprising address pairs of respective start addresses of the virtual pages and the associated physical pages.
In workstations, part of the page table is in a cache that is also referred to as “Translation Look Aside Buffer (TLB)”. If the start address pair for a virtual page and the associated physical page is in the TLB, then the calculation of the address mapping into the virtual memory area happens accelerated since only one access to a table is necessary in order to obtain the physical address associated to a virtual address.
If the start address pair, i.e. the virtual address and its associated physical address is in the TLB, then a TLB miss takes place, which usually leads to a trap to the operating system which has to add the address tupel to the TLB.
In the area of workstations, the mapping regulation between virtual address space and physical address space that can, for example, be implemented as a single page table, is held in the volatile working memory. When a workstation is booted up, it first starts in the real addressing mode. This means that the operating system of the workstation causes the CPU of the workstation to gradually set up a page table in the volatile working memory in the workstation in the real, i.e. physical addressing mode. Only when a page table is constructed, the workstation can switch to the virtual addressing mode. If the CPU asks for data at a virtual address, then the associated physical address is determined in the volatile working memory of the CPU in order to be able to fetch data from the memory. Common workstations are therefore distinguished by the fact that they boot up in a real addressing mode and then switch to the virtual addressing mode when the mapping regulation from the virtual address space to the physical address space in the volatile memory is set up.
It is one disadvantage of this concept that a relatively large working memory area is necessary in order to store a page table. This disadvantage is not of high importance for workstations, since they have large amounts of working memory available. For other applications, such as for security relevant computer systems, such as implemented in chip card ICs, the memory resources are limited due to the small available space. The provision of an amount of volatile working memory to store a page table leads to the fact that the application carried out on the chip card might have too little working memory and therefore experience performance losses.
It is another disadvantage of the known concept that a significant management effort is necessary to, at first, set up the page table when booting up the computer system, i.e. to gradually calculate the address allocations from the stored information and to store them. Besides the fact that computer resources are necessary for that, respective programs also have to be made available on a chip card in order to take the necessary precautions for the virtual addressing mode. Such programs also need memory space that is a limited resource, especially in chip cards or other security ICs, due to reasons of space.
In the specialist book “Computer Architecture: a quantitative approach” by David A. Patterson, second edition, 1996, Morgan Kaufmann Publishers, Inc., pages 449–453 the memory management of the alpha AXP processor is described. A hierarchical tree structure with three levels is used here as mapping regulation for determining a physical address from a virtual address. One node level comprises at least one node with a page table. The virtual address is divided into portions, wherein each portion of the virtual address is associated to a node level. The address translation begins with adding the highest-level address field to a page table base register, whereupon the memory is read out at this position to obtain the basis of the page table of the second level. The address field of the virtual address for the second level is then again added to this newly fetched address. Then the memory is accessed again to obtain the basis of the page table of the third level. The address field of the third level is added to this base address, whereupon the memory is read out by using this sum to obtain the physical address of the page that is referenced. A page offset is added to this address to obtain the physical address associated to the virtual address. Each page table in the alpha AXP architecture fits into a single page, so that all page table addresses are physical addresses that do not need any further translation. Each page table for each node level is therefore exactly one physical page long.
If the virtual address space is larger than the physical address space, which is especially an advantage when flexibility for future expansions of the physical address space is wanted, the page tables, i.e. the node lists of the nodes, contain a large number of zero entries, i.e. of entries that do not reference to a physical address or to no node of a lower node level. Due to the fact that each page table is exactly one physical memory page long, the known hierarchical addressing wastes a lot of memory space. The amount of wasted memory space is getting larger the larger the virtual address space is in comparison to the physical address space. The memory taken up by zero entries in the node lists leads to the fact that more memory space, for example in form of an external RAM has to be made available, especially in computer systems with limited memory resources, as they can be found on chip cards, smart cards or security ICs, which makes a chip card more expensive. If, however, due to reasons of chip space no further memory can be made available especially the working memory resources of the chip cards are more limited than absolutely necessary, which leads to the fact that less expensive programs can be computed in the chip card or that the performance of the chip card suffers.